This application claims priority from Korean Patent Application No. 2004-21147, filed on Mar. 29, 2004 in the Korean Intellectual Property Office, the disclosure of which is incorporated herein in its entirety by reference.
1. Field of the Invention
The present invention relates to hierarchical motion estimation of video data, and more particularly, to a middle level motion vector generation method and apparatus capable of reducing an amount of operations applied to a macroblock adaptive frame-field (MBAFF) mode.
2. Description of the Related Art
In motion estimation, which is a process for encoding video data, a macroblock in a past frame most similar to a macroblock in a current frame is searched by using a predetermined measurement function, so that a motion vector representing difference between positions of the macroblocks is generated. The criterion used to determine the most-similar macroblock is a matching reference value, which is a value of a predetermined measurement function. In general, the largest amount of operations is needed for the determination of the most-similar macroblock in the process for encoding video data.
The search process is a process for searching a block in the past frame most similar to the block of the current frame to be encoded in accordance with a predetermined search range and a predetermined block size. The search process is classified into a full search process and a local search process. The full search process is performed on all the portions of frames, and the local search process is performed on some portions of the previous frames based on a predetermined reference point.
Similarity between blocks of the past and current frames is determined by using all the pixel values in the past and current frames. A matching reference value is calculated by using the predetermined measurement function. The measurement function includes a Sum of Absolute Difference (SAD) function for obtaining a sum of absolute difference, a Sum of Absolute Transformed Difference (SATD) function for obtaining a sum of absolute transformed difference, and a Sum of Squared Difference (SSD) function for obtaining a sum of squared difference.
A large amount of operations for the calculation of the matching reference value is needed. Accordingly, much hardware resource is needed to implement real-time video data encoding. The hierarchical motion estimation technique has been developed in order to reduce the amount of operations in the motion estimation. In the hierarchical motion estimation technique, an original frame is divided into frames having different resolutions and motion vectors corresponding to the frames having the different resolutions are hierarchically generated. The most widely known method used for the hierarchical motion estimation technique is a multi-resolution multiple candidate searching (MRMCS) method.
FIG. 1 is a conceptual view of conventional hierarchical motion estimation. A middle level motion estimation process is performed in multiple levels: a lower level 104 where blocks of the to-be-encoded current and past frames have the same resolution as that of an original image; a middle level 102 where the resolution is reduced by decimating the original image in the lower level 104 with a decimation ratio of 2:1 (horizontal:vertical); and an upper level 100 where the resolution is further reduced by decimating the image decimated in the middle level with a decimation ratio of 2:1. In the hierarchical motion estimation, the motion estimation is performed in the levels by using three images having different resolutions, so that the motion estimation can be preformed at a high speed.
Now, the conventional hierarchical motion estimation will be described in detail. In the motion estimation, it is assumed that the motion estimation is performed in units of a macroblock having a size of 16×16 and a search range in the motion estimation is [−16, +16]. The hierarchical motion estimation comprises three steps as follows.
In the first step, a search process is performed in the upper level to search a block of the past frame having a size of 4×4 (¼ of an original size) matching with a current block having a size of 4×4 (¼ of the original size). The search range in the upper level is [−4, 4] (¼ of the original search range). In general, an SAD function is used as a measurement function for the matching reference values. Based on the results of the search process in the upper level, two blocks firstly and secondly matching with the current block are determined, and motion vectors for the two blocks are obtained.
In the second step, a median motion vector is calculated from three motion vectors of three neighboring macroblocks located at left, right, and upper right sides of the current macroblock at lower level. The motion vectors of the three neighboring macroblocks are determined in advance. The median motion vector is the median value of the three motion vectors.
Next, one block most matching with the current block and the corresponding motion vector are obtained by performing a local search process over a search range of [−2, +2] on a past frame having ½ of the original size based on three points including the two upper left corner points of the two blocks determined in the middle level 102 and one point indicated by the median motion vector.
In the third step, one macro block most matching with the current macroblock and the corresponding motion vector are finally obtained by performing a local search process over a search range of [−2, 2] on the past frame in the lower level 104, that is, the past frame having an original size based on an upper left corner point of one block determined in the middle level 102.
On the other hand, in the current motion picture standards including the H.264 and MPEG2 standards, field motion estimation as well as frame motion estimation is employed in order to support an interlacing scan scheme. In particular, the H.264 and MPEG2 standards support the NBAFF mode where the frame and field motion estimation processes are performed in units of not a picture but a macroblock.
However, if the aforementioned hierarchical motion estimation scheme is simply applied to the motion picture standards supporting the MBAFF mode, the amount of operations drastically increases because the middle level motion vector is obtained by separately calculating matching reference values for the frame and field motion estimation processes.